package hwOne3;

import edu.princeton.cs.algs4.Stack;

/**
 * 作业 1.3.4
 */
public class Parentheses {

    // 检查括号是否匹配的方法
    public static boolean isBalanced(String input) {
        Stack<Character> stack = new Stack<>(); // 创建一个栈来存储括号

        for (char c : input.toCharArray()) { // 遍历输入字符串中每个字符
            // 如果是左括号，压入栈
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }
            // 如果是右括号，检查是否匹配
            else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false; // 如果栈为空，说明没有匹配的左括号
                }
                char top = stack.pop(); // 弹出栈顶的左括号
                if (!isMatchingPair(top, c)) {
                    return false; // 如果不匹配，返回false
                }
            }
        }

        // 检查栈是否为空，如果为空，说明所有括号匹配完成
        return stack.isEmpty();
    }

    // 判断两个括号是否匹配
    private static boolean isMatchingPair(char open, char close) {
        return (open == '(' && close == ')') ||
                (open == '[' && close == ']') ||
                (open == '{' && close == '}');
    }

    public static void main(String[] args) {
        // 从标准输入读取字符串
        System.out.println("请输入括号字符串：");
        java.util.Scanner scanner = new java.util.Scanner(System.in);
        String input = scanner.nextLine();
        scanner.close();

        // 检查括号是否匹配
        if (isBalanced(input)) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }
}